/* 排序和搜索算法练习题参考答案（C语言实现）*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

// ========== 工具函数 ==========

// 交换两个整数
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 打印数组
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 创建随机数组
void createRandomArray(int arr[], int n, int min, int max)
{
    srand(time(NULL));
    for (int i = 0; i < n; i++)
    {
        arr[i] = min + rand() % (max - min + 1);
    }
}

// ========== 排序算法 ==========

// 1. 冒泡排序
void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break; // 优化：如果一轮没有交换，说明已排序
    }
}

// 2. 选择排序
void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        if (minIndex != i)
        {
            swap(&arr[i], &arr[minIndex]);
        }
    }
}

// 3. 插入排序
void insertionSort(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 4. 希尔排序
void shellSort(int arr[], int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; i++)
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
            {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

// 归并排序辅助函数
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 5. 归并排序
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

// 快速排序辅助函数
int partition(int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 6. 快速排序
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 堆排序辅助函数
void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

// 7. 堆排序
void heapSort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--)
    {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

// 8. 计数排序（假设数据范围较小）
void countingSort(int arr[], int n, int max)
{
    int output[n];
    int count[max + 1];

    // 初始化计数数组
    for (int i = 0; i <= max; i++)
        count[i] = 0;

    // 统计每个元素出现次数
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // 累计计数
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    // 构建输出数组
    for (int i = n - 1; i >= 0; i--)
    {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 复制回原数组
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// ========== 搜索算法 ==========

// 1. 顺序搜索
int linearSearch(int arr[], int n, int key)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == key)
        {
            return i; // 找到元素，返回索引
        }
    }
    return -1; // 未找到元素
}

// 2. 二分搜索（要求数组已排序）
int binarySearch(int arr[], int l, int r, int key)
{
    while (l <= r)
    {
        int mid = l + (r - l) / 2;

        if (arr[mid] == key)
        {
            return mid;
        }

        if (arr[mid] < key)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return -1; // 未找到元素
}

// 3. 插值搜索（要求数组已排序，分布均匀）
int interpolationSearch(int arr[], int n, int key)
{
    int lo = 0, hi = n - 1;

    while (lo <= hi && key >= arr[lo] && key <= arr[hi])
    {
        if (lo == hi)
        {
            if (arr[lo] == key)
                return lo;
            return -1;
        }

        // 估算位置
        int pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (key - arr[lo]));

        if (arr[pos] == key)
        {
            return pos;
        }

        if (arr[pos] < key)
        {
            lo = pos + 1;
        }
        else
        {
            hi = pos - 1;
        }
    }
    return -1; // 未找到元素
}

// 4. 斐波那契搜索（要求数组已排序）
int fibonacciSearch(int arr[], int n, int key)
{
    int fibMMm2 = 0;
    int fibMMm1 = 1;
    int fibM = fibMMm2 + fibMMm1;

    while (fibM < n)
    {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }

    int offset = -1;

    while (fibM > 1)
    {
        int i = offset + fibMMm2;

        if (i >= n || arr[i] > key)
        {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        }
        else if (arr[i] < key)
        {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        }
        else
        {
            return i;
        }
    }

    if (fibMMm1 == 1 && offset + 1 < n && arr[offset + 1] == key)
    {
        return offset + 1;
    }

    return -1; // 未找到元素
}

// ========== 测试函数 ==========

void testSortingAlgorithms()
{
    int n = 10;
    int arr[n];
    int temp[n];

    printf("===== 测试排序算法 =====\n");

    // 创建随机数组
    createRandomArray(arr, n, 1, 100);
    printf("原始数组: ");
    printArray(arr, n);

    // 测试冒泡排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    bubbleSort(temp, n);
    printf("冒泡排序: ");
    printArray(temp, n);

    // 测试选择排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    selectionSort(temp, n);
    printf("选择排序: ");
    printArray(temp, n);

    // 测试插入排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    insertionSort(temp, n);
    printf("插入排序: ");
    printArray(temp, n);

    // 测试希尔排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    shellSort(temp, n);
    printf("希尔排序: ");
    printArray(temp, n);

    // 测试归并排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    mergeSort(temp, 0, n - 1);
    printf("归并排序: ");
    printArray(temp, n);

    // 测试快速排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    quickSort(temp, 0, n - 1);
    printf("快速排序: ");
    printArray(temp, n);

    // 测试堆排序
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    heapSort(temp, n);
    printf("堆排序: ");
    printArray(temp, n);

    // 测试计数排序（只适用于较小范围的数据）
    printf("计数排序: ");
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    countingSort(temp, n, 100);
    printArray(temp, n);

    printf("\n");
}

void testSearchingAlgorithms()
{
    int n = 10;
    int arr[n];

    printf("===== 测试搜索算法 =====\n");

    // 创建有序数组
    createRandomArray(arr, n, 1, 100);
    quickSort(arr, 0, n - 1);
    printf("有序数组: ");
    printArray(arr, n);

    // 测试搜索
    int key = arr[5]; // 选择一个已知存在的元素
    printf("搜索元素: %d\n", key);

    int result1 = linearSearch(arr, n, key);
    printf("顺序搜索: 索引 = %d\n", result1);

    int result2 = binarySearch(arr, 0, n - 1, key);
    printf("二分搜索: 索引 = %d\n", result2);

    int result3 = interpolationSearch(arr, n, key);
    printf("插值搜索: 索引 = %d\n", result3);

    int result4 = fibonacciSearch(arr, n, key);
    printf("斐波那契搜索: 索引 = %d\n", result4);

    // 测试不存在的元素
    key = 200; // 这个元素应该不存在
    printf("\n搜索不存在的元素: %d\n", key);
    result1 = linearSearch(arr, n, key);
    printf("顺序搜索: 索引 = %d\n", result1);

    printf("\n");
}

// ========== 性能测试函数 ==========

void performanceTest()
{
    int sizes[] = {1000, 10000, 100000};

    printf("===== 性能测试 =====\n");

    for (int s = 0; s < 3; s++)
    {
        int n = sizes[s];
        printf("数组大小: %d\n", n);

        // 分配内存
        int *arr = (int *)malloc(n * sizeof(int));
        int *temp = (int *)malloc(n * sizeof(int));

        // 创建随机数组
        createRandomArray(arr, n, 1, 10000);

        // 测试快速排序性能
        for (int i = 0; i < n; i++)
            temp[i] = arr[i];
        clock_t start = clock();
        quickSort(temp, 0, n - 1);
        clock_t end = clock();
        double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        printf("快速排序: %.6f 秒\n", time_taken);

        // 测试归并排序性能
        for (int i = 0; i < n; i++)
            temp[i] = arr[i];
        start = clock();
        mergeSort(temp, 0, n - 1);
        end = clock();
        time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        printf("归并排序: %.6f 秒\n", time_taken);

        // 测试堆排序性能
        for (int i = 0; i < n; i++)
            temp[i] = arr[i];
        start = clock();
        heapSort(temp, n);
        end = clock();
        time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        printf("堆排序: %.6f 秒\n", time_taken);

        // 释放内存
        free(arr);
        free(temp);

        printf("\n");
    }
}

int main()
{
    // 测试排序算法
    testSortingAlgorithms();

    // 测试搜索算法
    testSearchingAlgorithms();

    // 性能测试（可选，对较大数组进行测试）
    performanceTest();

    printf("所有测试完成！\n");
    return 0;
}

/*
## 代码说明

### 排序算法实现

1. **冒泡排序**：通过重复遍历数组，比较相邻元素并交换顺序，每次将最大元素冒泡到末尾。
    - 时间复杂度：O(n²)，最好情况O(n)
    - 空间复杂度：O(1)
    - 稳定性：稳定

2. **选择排序**：每次从未排序部分选择最小元素，放到已排序部分的末尾。
    - 时间复杂度：O(n²)
    - 空间复杂度：O(1)
    - 稳定性：不稳定

3. **插入排序**：将元素逐一插入到已排序序列的正确位置。
    - 时间复杂度：O(n²)，最好情况O(n)
    - 空间复杂度：O(1)
    - 稳定性：稳定

4. **希尔排序**：插入排序的改进版，通过比较相距一定间隔的元素进行排序，逐步减小间隔。
    - 时间复杂度：O(n^1.3) ~ O(n²)
    - 空间复杂度：O(1)
    - 稳定性：不稳定

5. **归并排序**：采用分治法，将数组分成两半，分别排序后再合并。
    - 时间复杂度：O(nlogn)
    - 空间复杂度：O(n)
    - 稳定性：稳定

6. **快速排序**：选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归排序。
    - 时间复杂度：O(nlogn)，最坏情况O(n²)
    - 空间复杂度：O(logn)
    - 稳定性：不稳定

7. **堆排序**：利用堆数据结构进行排序，每次将最大元素移到末尾。
    - 时间复杂度：O(nlogn)
    - 空间复杂度：O(1)
    - 稳定性：不稳定

8. **计数排序**：非比较排序算法，适用于范围较小的整数排序。
    - 时间复杂度：O(n+k)，k为数据范围
    - 空间复杂度：O(k)
    - 稳定性：稳定

### 搜索算法实现

1. **顺序搜索**：从数组开头逐个检查元素。
    - 时间复杂度：O(n)

2. **二分搜索**：要求数组已排序，每次将搜索范围减半。
    - 时间复杂度：O(logn)

3. **插值搜索**：二分搜索的改进，根据元素值的分布估算位置。
    - 时间复杂度：O(loglogn) 到 O(n)

4. **斐波那契搜索**：使用斐波那契数列进行分割，避免了乘法和除法操作。
    - 时间复杂度：O(logn)

### 使用说明

1. 代码提供了多种排序和搜索算法的实现，可以根据具体需求选择合适的算法。
2. 对于小规模数据，简单排序算法（如插入排序）可能比复杂算法更高效。
3. 对于大规模数据，应选择O(nlogn)的排序算法。
4. 搜索算法中，二分搜索是最常用的高效搜索方法，但要求数组必须有序。
5. 性能测试函数可以比较不同算法在不同数据规模下的效率差异。

### 注意事项

1. 代码中简化了一些错误处理，实际应用中可能需要更完善的错误检查。
2. 计数排序仅适用于整数且范围较小的情况。
3. 二分搜索、插值搜索和斐波那契搜索要求数组必须有序。
4. 在实际应用中，应根据数据特点和需求选择最合适的算法。*/
